# 回溯法求解n皇后问题
from time import time


sc = 0

def queen(n: int) -> int:
    global sc
    # x[i]表示第i行放置皇后的列下标，-1表示未放置      
    x, k, count = [-1] * n, 0, 0

    # 循环模拟递归，摆放皇后k
    while k >= 0:
        sc += 1           
        x[k] += 1
        while x[k] < n and any(x[i] == x[k] or abs(i - k) == abs(x[i] - x[k]) for i in range(k)):
            x[k] += 1
        
        if x[k] < n and k == n - 1:
            # print('  '.join(map(str, x)))
            count += 1
        if x[k] < n and k < n - 1:
            k = k + 1
        else:
            x[k] = -1
            k -= 1
    
    # 最后返回总共有多少组解
    return count

# mian
T = time()
ans = queen(16)
print('共有', ans, '个解!')
T = time() - T
print('sc=', sc, ' T=', T, 'sec')

